package com.zhao.utils;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

import com.zhao.po.Car;
import com.zhao.po.Product;

/**
 * 贪心算法－背包算法： 背包算法是从一堆里面选择出最多能容纳的。 我们要
 */
public class BackPackageUtil {

	private BigDecimal[] weights;// 物品重量

	private BigDecimal[] values;// 物品体积

	private Car car;

	private List<Product> products;

	public BackPackageUtil(Car car, List<Product> products) {
		super();

		this.car = car;
		this.products = products;
		int size = this.products.size();
		// 初始化属性的值
		this.weights = new BigDecimal[size];
		this.values = new BigDecimal[size];

		for (int i = 0; i < size; i++) {
			Product product = products.get(i);
			this.weights[i] = product.getProductwith();
			this.values[i] = product.getProductheight().multiply( product.getProductlenth()).multiply(product.getProductwith()) ;
		}
	}

	/**
	 * 根据物品重量和物品价值，求出每个物品的性价比－》将性价比进行排序－》选取性价比最高的物品添加到背包中－》直到背包不能再添加
	 */

	// 返回能装入车中的物品。 这里要实现的就是从items中取出不能装入的。
	public List<Product> backpack() {
		List<Product> backList = new ArrayList<Product>();
		// step1:求物品性价比－》并从大到小排序
		// 这里需要考虑怎么计算性价比
		int size = weights.length;// 物品数量
		BigDecimal[] prices = new BigDecimal[size];// 每个物品的性价比(每kg的价值)

		// 用一个数组用于保存排序后的性价比和最开始的物品重量的下标
		int[] tags = new int[size];
		for (int i = 0; i < size; i++) {
			prices[i] = values[i].divide(weights[i]) ;
			tags[i] = i;// 默认排序
		}

		// 选择排序
		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				if (-1==prices[i].compareTo(prices[j])) {
					// 交换
					BigDecimal temp = prices[i];
					prices[i] = prices[j];
					prices[j] = temp;

					int tag = tags[i];
					tags[i] = tags[j];
					tags[j] = tag;
				}
			}
		}

		BigDecimal capacity = car.getMaxweight();
		// 根据已经从大到小排好序的性价比，和相对应的重量和价值，添加到背包中
		for (int i = 0; i < size; i++) {
			// 根据tags数组中重量的下标，拿到重量
			if (-1== weights[tags[i]].compareTo(capacity) ) {

				// 这里怎么将商品添加到新的集合? 怎么获取对应的item对象。 在这里我们能拿到的就是i
				Product item = this.products.get(i);

				// 这里还要加上一个判断： 判断这个商品是否能添加进车，这里需要做一个判断
				if (canFillItem(item)) {
					backList.add(item);
				}
				capacity = capacity.subtract(weights[tags[i]]);
			}
		}

		return backList;
	}

	/**
	 * 判断这个商品能否装车
	 * 
	 * @return
	 */
	private Boolean canFillItem(Product item) {

		return (maxOfThree(item.getProductheight(), item.getProductlenth(), item.getProductwith()).compareTo(maxOfThree(
				this.car.getCarheight(), this.car.getCarlength(), this.car.getCarwith()))==-1 ) ;
     
	}

	private BigDecimal maxOfThree(BigDecimal a, BigDecimal b, BigDecimal c) {
		BigDecimal max;
		if (a.compareTo(b)==1  && a.compareTo(c)==1 ) {
			max = a;
		} else if (c.compareTo(a)==1 && c.compareTo(b)==1) {
			max = c;
		} else {
			max = b;
		}
		return max;
	}

}
